class Solution
{
    bool checkRow[9][10], checkCol[9][10];
    bool check[3][3][10];
public:
    void solveSudoku(vector<vector<char>>& board)
    {
        for (int i = 0; i < 9; ++i)
            for (int j = 0; j < 9; ++j)
                if (board[i][j] != '.')
                {
                    int num = board[i][j] - '0';
                    checkRow[i][num] = true;
                    checkCol[j][num] = true;
                    check[i / 3][j / 3][num] = true;
                }
        dfs(board);
        return;
    }

    bool dfs(vector<vector<char>>& board)
    {
        for (int i = 0; i < 9; ++i)
        {
            for (int j = 0; j < 9; ++j)
            {
                if (board[i][j] == '.')
                {
                    for (int k = 1; k <= 9; ++k)
                    {
                        if (!checkRow[i][k] && !checkCol[j][k] && !check[i / 3][j / 3][k])
                        {
                            board[i][j] = k + '0';
                            checkRow[i][k] = true;
                            checkCol[j][k] = true;
                            check[i / 3][j / 3][k] = true;
                            if (dfs(board))
                                return true;
                            board[i][j] = '.';
                            checkRow[i][k] = false;
                            checkCol[j][k] = false;
                            check[i / 3][j / 3][k] = false;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
};